// Copyright 2012 Google Inc. All Rights Reserved.  -*- C++ -*-
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "benchmark.h"
#include <algorithm>
#include <numeric>
#include <deque>
#include <range>
#include <range_algorithm>

namespace {

struct GreaterThan {
  const int compare;
  GreaterThan(int c) : compare(c) {}
  bool operator()(int value) { return value > compare; }
};

void benchmark_drop_until() {
  BenchmarkGroup drop_bm;
  const int kNumValues = 50 * 1000 * 1000;
  std::deque<int> values(kNumValues);
  std::iota(values.begin(), values.end(), 0);

  {
    std::range<std::deque<int>::const_iterator> cheap_range(values);
    Benchmark drop_cheap_range(drop_bm, "drop_until on cheap range");
    drop_cheap_range.start();
    for (int i = 0; i < kNumValues; i = source(i + 10)) {
      cheap_range = std::drop_until(cheap_range, GreaterThan(i));
    }
    drop_cheap_range.stop();
  }

  {
    std::deque<int>::const_iterator first(values.begin());
    Benchmark find_iter(drop_bm, "find on cheap range");
    find_iter.start();
    for (int i = 0; i < kNumValues; i = source(i + 10)) {
      first = std::find_if(first, values.cend(), GreaterThan(i));
    }
    find_iter.stop();
  }

  {
    std::deque<int> expensive_range(values);
    Benchmark drop_expensive_range(drop_bm, "drop_until on expensive range");
    drop_expensive_range.start();
    for (int i = 0; i < kNumValues; i = source(i + 10)) {
      expensive_range = std::drop_until(std::move(expensive_range), GreaterThan(i));
    }
    drop_expensive_range.stop();
  }

  {
    std::deque<int> expensive_range(values);
    Benchmark loop_expensive_range(drop_bm, "loop through expensive range");
    loop_expensive_range.start();
    for (int i = 0; i < kNumValues; i = source(i + 10)) {
      while(!expensive_range.empty() &&
            !GreaterThan(i)(expensive_range.front()))
        expensive_range.pop_front();
    }
    loop_expensive_range.stop();
  }
}

}  // anonymous namespace

int main() {
  benchmark_drop_until();
}

